#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#define eps 1e-12
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define UPCASE(c) (((c)>='a'&&(c)<='z')?((c)-0x20):(c) ) 
#define DOWNCASE(c) (((c)>='A'&&(c)<='Z')?((c)+0x20):(c) )
#define ll long long
struct node{
	int key;
	char c;
	struct node* link;
};
struct indexTable{
	int maxKey;
	struct node* link;
};
struct node *creatList_block(int nodeNum){
	int t;
	char c;
	struct node *head,*p,*q;
	std::cin>>t>>c;
	head= (struct node*)malloc(sizeof(struct node));  
	head->key=t;
	head->c=c;
	head->link=NULL;
	q=head;
	for(int i=1;i<nodeNum;i++){
		std::cin>>t>>c;
		p=(struct node*)malloc(sizeof(struct node));
		p->c=c;
		p->key=t;
		p->link=0;
		q->link=p;
		q=p;	
	}
	return head;
}
void creatBlockStruct(struct indexTable s[],int n){
	struct node *z;
	for(int i=0;i<n;i++){
		printf("Enter the number in the %d block",i+1);//n个块，每个块中number个结点
		int number;
		scanf("%d",&number);
		s[i].link=creatList_block(number);
		
		z=s[i].link;
		int maxKey=0;
		while(z!=0){
			if(z->key>maxKey)
				maxKey=z->key;
			z=z->link;	
		}
		s[i].maxKey=maxKey;
		
	}
}
void blockSearch(indexTable s[], int n, int key) {  
    int i;  
    for (i = 0; i < n; i++) {  
        if (key <= s[i].maxKey)  
            break;  
    }  
    // 检查 i 是否是一个有效的索引  
    if (i == n) {  
        printf("Key not found in any block.\n");  
        return;  
    }  
    struct node *p = s[i].link;  
    int t=0;
    while (p != NULL) {  
        if ((p->key) == key) {
			t++;  
            printf("%d %d %d\n",key, i, t);  
            return;  
        }  
        t++;
        p = p->link;  
    }  
    printf("Key not found in block %d.\n", i);  
}
void freeList(struct node* head) {  
    struct node* temp;  
    while (head != NULL) {  
        temp = head;  
        head = head->link;  
        free(temp);  
    }  
}  
  
void freeBlockStruct(struct indexTable s[], int n) {  
    for (int i = 0; i < n; i++) {  
        freeList(s[i].link);  
    }  
}  
int main()
{
   struct indexTable s[100];
   printf("Please enter the number of blocks:");
   int n;
   scanf("%d",&n);
   creatBlockStruct(s,n);
   printf("Please enter the number you want to find:");
   int key;
   scanf("%d",&key);
   blockSearch(s,n,key);
   freeBlockStruct(s, n);
   return 0;
}
